N = 10**6+1
is_prime = [1]*N
is_prime[0] = 0
is_prime[1] = 0
def sieve():
i = 2
while i*i <= N:
if is_prime[i] == 0:
i += 1
continue
j = 2*i
while j < N:
is_prime[j] = 0
j += i
i += 1
sieve()
lstp=[]
for i in range(1, N):
if is_prime[i] == 1:
lstp.append(i)
se=set(lstp)
t=int(input())
for i in range(t):
n,e=map(int,input().split())
lst=list(map(int,input().split()))
ones=[]
primes=[]
for j in range(n):
ele=lst[j]
if ele==1:
ones.append(j+1)
elif ele in se:
primes.append(j+1)
c=0
for j in primes:
ele=lst[j-1]
right=0
left=0
for f in range(j+e-1,n,e):
if lst[f]==1:
right+=1
else:
break
for f in range(j-e-1,-1,-e):
if lst[f]==1:
left+=1
else:
break
c+=(((left+1)*(right+1))-1)
print(c)#include<bits/stdc++.h>
#define ORIGNAL_SENSEI ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
typedef long double ld;
const ll MOD=1e9+7, OO=0x3f3f3f3f;
const ll LOO=0x3f3f3f3f3f3f3f3f;
#define all(x) (x).begin(),(x).end()
#define mm(f, x) memset(f,x,sizeof(f))
#define f(n) for(int i=0;i<n;++i)
#define fa(i,a,n) for(int i=(a);i<=(n);++i)
#define c(vec) for(auto &x:vec)cin>>x;
#define ff(vec) for(auto &x:vec)cout<<x<<' ';cout<<'\n';
#define debug(x) cout<<#x<<":"<<x<<endl;
#define yes cout<<"YES\n";
#define no cout<<"NO\n";
//#define f(n,m) for(int i=0;i<n;i++)for(int j=0;j<m;j++)
const long double EPS=1e-8;
const ll MOD1=1e18+7;
int dr[]={-1, -1, -1, 0, 1, 1, 1, 0};
int dc[]={-1, 0, 1, 1, 1, 0, -1, -1};
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
int prime[1000005];
void sieve(){
prime[0]=prime[1]=1;
for(int i=2;i*i<1000001;i+=((i%2)+1)){
if(prime[i]==0)
for(int j=i*i;j<1000001;j+=i){
prime[j]=1;
}
}
}
int main() {
ORIGNAL_SENSEI
//freopen("input.txt","rt",stdin);
//freopen("output.txt","wt",stdout);
int t;
cin>>t;
sieve();
while(t--){
int n,e;
cin>>n>>e;
vector<int>vec(n);
c(vec)
vector<int>ans;
f(n){
if(prime[vec[i]]==0)ans.push_back(i);
}
map<ll,ll>mp;
for(auto i:ans){
ll cnt=0;
ll val=vec[i];
if(val==1) {
bool flag=0;
for (int j = i + e; j < n; j += e) {
if(flag&&vec[j]==1)cnt++;
else if(vec[j]==1)continue;
else if(prime[vec[j]]==1||flag)break;
else if(prime[vec[j]]==0){
cnt++;
flag=1;
}
}
}
else if(prime[val]==0){
for (int j = i + e; j < n; j += e) {
if(vec[j]==1)cnt++;
else break;
}
}
mp[i]=cnt;
}
for(auto i:ans){
ll c=0;
ll val=vec[i];
if(val==1) {
bool flag=0;
for (int j = i - e; j >= 0; j -= e) {
if(flag&&vec[j]==1)c++;
else if(vec[j]==1)continue;
else if(prime[vec[j]]==1||flag)break;
else if(prime[vec[j]]==0){
c++;
flag=1;
}
}
}
else if(prime[val]==0){
for (int j = i - e; j >=0; j -= e) {
if(vec[j]==1)c++;
else break;
}
}
if(c!=0){
mp[i]+=(c*mp[i]+c);
}
}
ll cnt=0;
for(auto x:mp)cnt+=x.second;
cout<<cnt<<'\n';
}
}102. Binary Tree Level Order Traversal | 96. Unique Binary Search Trees |
75. Sort Colors | 74. Search a 2D Matrix |
71. Simplify Path | 62. Unique Paths |
50. Pow(x, n) | 43. Multiply Strings |
34. Find First and Last Position of Element in Sorted Array | 33. Search in Rotated Sorted Array |
17. Letter Combinations of a Phone Number | 5. Longest Palindromic Substring |
3. Longest Substring Without Repeating Characters | 1312. Minimum Insertion Steps to Make a String Palindrome |
1092. Shortest Common Supersequence | 1044. Longest Duplicate Substring |
1032. Stream of Characters | 987. Vertical Order Traversal of a Binary Tree |
952. Largest Component Size by Common Factor | 212. Word Search II |
174. Dungeon Game | 127. Word Ladder |
123. Best Time to Buy and Sell Stock III | 85. Maximal Rectangle |
84. Largest Rectangle in Histogram | 60. Permutation Sequence |
42. Trapping Rain Water | 32. Longest Valid Parentheses |
Cutting a material | Bubble Sort |